Integrating tabu search and VLSN search to develop enhanced algorithms: A case study using bipartite boolean quadratic programs

摘要

The bipartite boolean quadratic programming problem (BBQP) is ageneralization of the well studied boolean quadratic programming problem. Themodel has a variety of real life applications; however, empirical studies ofthe model are not available in the literature, except in a few isolatedinstances. In this paper, we develop efficient heuristic algorithms based ontabu search, very large scale neighborhood (VLSN) search, and a hybridalgorithm that integrates the two. The computational study establishes thateffective integration of simple tabu search with VLSN search results insuperior outcomes, and suggests the value of such an integration in othersettings. Complexity analysis and implementation details are provided alongwith conclusions drawn from experimental analysis. In addition, we obtainsolutions better than the best previously known for almost all medium and largesize benchmark instances.